package basic;

import java.util.ArrayList;

import javax.vecmath.Matrix3d;


public class BoxTree {

	private CrtMesh meshes;

	private BoxTree left;
	private BoxTree right;
	private String tag;
	private final ArrayList<Polygon> polys= new ArrayList<Polygon>();
	private Box bound=null;

	/**
	 * Costruttore ricorsivo della gerarchia di box
	 * @param meshes
	 */
	public BoxTree(CrtMesh meshes) {
		this.meshes=meshes;
		bound=new Box(meshes);
		Plane plane= select(meshes);
		int white = 0, blue = meshes.size();
		while (white < blue) {
			double b=0,e=0;
			double[] array=meshes.getPolygon().get(white).interval(plane, b, e);
			b=array[0];
			e=array[1];
			if (b + e < 0) ++white;
			else 
				meshes.getPolygon().get(--blue).swap(meshes.getPolygon().get(white));
		}
		if (blue == 0 || blue == meshes.size()) {
			this.tag="LEAF";
			this.polys.addAll(meshes.getPolygon());
		}
		else {
			this.tag="INTERNAL";
			this.left = new BoxTree(getSubArrayPrimitive(meshes.getPolygon(),0,white));
			this.right = new BoxTree(getNewMesh(blue,meshes.getPolygon()));
		}
	}

	private CrtMesh getNewMesh(int index, ArrayList<Polygon> list)
	{
		CrtMesh temp= new CrtMesh("torus");
		temp.clearMesh();
		for(int i=index; i<list.size();i++) temp.addMeshPrimitive(list.get(i));
		return temp;
	}

	private  CrtMesh getSubArrayPrimitive(ArrayList<Polygon> array,int start,int end)
	{
		CrtMesh temp= new CrtMesh("torus");
		temp.clearMesh();
		for(int i=start; i<end; ++i) temp.addMeshPrimitive(array.get(i));
		return temp;
	}

	/**
	 * Metodo per la selezione del piano di partizionamento
	 * @param meshes
	 * @return
	 */
	private Plane select(CrtMesh meshes)
	{
		int axis=new Box(meshes).longestAxis();
		double median=0;
		for (int i = 0; i < meshes.size(); ++i) {
			double mid = 0;
			for (int j = 0; j < meshes.getPolygon().get(i).size(); ++j)  
				mid += meshes.getPolygon().get(i).getVertex(j).dblposition().getAxis(axis);
			median+=mid/meshes.getPolygon().get(i).size();
		}
		Plane plane= new Plane();
		double a= (axis==0) ? 1 : 0;
		double b= (axis==1) ? 1 : 0;
		double c= (axis==2) ? 1 : 0;
		plane.setValue(a, b, c, median/meshes.size());
		return plane;
	}

	/**
	 * Metodo ricorsivo per la verifica delle collisioni tra due gerarchie
	 * @param tree1
	 * @param tree2
	 * @param t
	 * @param m
	 * @return
	 */
	public static boolean intersect(BoxTree tree1,BoxTree tree2,Transform t, Matrix3d m)
	{
		if (!Box.intersect(tree1.bound,tree2.bound, t, m)) {
			return false;
		}
		if(tree1.isLeaf() && tree2.isLeaf())
		{
			for (int j = 0; j < tree2.size(); ++j) 
			{
				Polygon poly= new Polygon(tree2.polys.get(j),t);
				for (int i = 0; i < tree1.size(); ++i)
					if(Polygon.intersect(tree1.polys.get(i),poly)) {
					
						return true;
					}
				return false;
			}

		}else if(tree1.isLeaf() || (!tree2.isLeaf() && tree1.bound.size() < tree2.bound.size()))
		{
			return BoxTree.intersect(tree1,tree2.left,t, m) || BoxTree.intersect(tree1,tree2.right, t, m); 

		}
		return BoxTree.intersect(tree1.left,tree2, t, m) || BoxTree.intersect(tree1.right,tree2, t, m);
	}

	public String toString() {
		String ret = "";
		if (this.left != null) ret += this.left.toString();
		if (this.right != null) ret += this.right.toString();
		if (this.bound != null) ret += this.bound.toString();
		return ret;
	}

	public String getLeaf() {
		String ret = "";
		if (this.left != null) ret += this.left.getLeaf();
		if (this.right != null) ret += this.right.getLeaf();
		if (this.isLeaf()) ret += "LEAF:\n"+this.LeaftoString();
		return ret;
	}

	public boolean isLeaf()
	{
		if(this.tag=="LEAF") return true;
		else return false;
	}

	public int size()
	{
		return this.polys.size();
	}

	public String LeaftoString() {
		String str = "";
		if (this.tag == "LEAF") for (int i = 0; i < this.polys.size(); i++) str += this.polys.get(i).toString()+"\n";
		return str;
	}

}
